#include <vector>
#include <list>
#include <assert.h>

using namespace std;

class HashTable1 {

    vector< list< int > > map_;
    
  public:
    HashTable1() 
	    : map_( 10 ) {
    }

    void insert( int i ) {
	// allows double insert
	map_[ i % 10 ].push_front( i );
    }

    void remove( int i ) {
	list< int > &l = map_[ i % 10 ];
	for ( list< int >::iterator it = l.begin();
	      l.end() != it; it++ ) {
	    if ( *it == i ) {
		l.erase( it );
		break;
	    }
	}
    }

    bool contains( int i ) {
	list< int > &l = map_[ i % 10 ];
	for ( list< int >::iterator it = l.begin();
	      l.end() != it; it++ ) {
	    if ( *it == i ) return true;
	}
	return false;
    }
};

class HashTable2 {

    struct Entry {
	int key; 
	int val;

	Entry( int k, int v ) 
		: key( k ),
		  val( v ) {
	}
    };

    vector< list< Entry > > map_;
    
  public:
    HashTable2() 
	    : map_( 10 ) {
    }

    void insert( int key, int val ) {
	// allows double insert
	map_[ key % 10 ].push_front( Entry( key, val ) );
    }

    void remove( int key ) {
	list< Entry > &l = map_[ key % 10 ];
	for ( list< Entry >::iterator it = l.begin();
	      l.end() != it; it++ ) {
	    if ( it->key == key ) {
		l.erase( it );
		break;
	    }
	}
    }

    bool contains( int key ) {
	list< Entry > &l = map_[ key % 10 ];
	for ( list< Entry >::iterator it = l.begin();
	      l.end() != it; it++ ) {
	    if ( it->key == key ) return true;
	}
	return false;
    }

    int find( int key ) {
	list< Entry > &l = map_[ key % 10 ];
	for ( list< Entry >::iterator it = l.begin();
	      l.end() != it; it++ ) {
	    if ( it->key == key ) return it->val;
	}
	throw "fool";
    }
};

int main( int argc, char *argv[] ) {

    {
	HashTable1 ht;

	// srand( 1 );

	// vector< int > nums
    
	ht.insert( 4 );
	assert( ht.contains( 4 ) );
	assert( !ht.contains( 5 ) );

	ht.remove( 4 );
	assert( !ht.contains( 4 ) );
    }
    
    {
	HashTable2 ht2;
    
	ht2.insert( 4, 0 );
	assert( ht2.contains( 4 ) );
	assert( !ht2.contains( 5 ) );

	assert( ht2.find( 4 ) == 0 );
	ht2.remove( 4 );
	assert( !ht2.contains( 4 ) );

    }
}
